#Include ../debug.ahk
#Include queue.ahk

class TreeNode {
  __New(val) {
    this.val := val
    this.left := ''
    this.right := ''
  }

  AppendLeft(val) {
    node := TreeNode(val)
    this.left := node
    return node
  }

  AppendRight(val) {
    node := TreeNode(val)
    this.right := node
    return node
  }
}

class Tree {
  __New(val) {
    this.root := TreeNode(val)
  }

  ; param: node's value
  ; ret:   node
  ; desc:  append the left node and return this node
  AppendLeft(val) {
    node := this.root.AppendLeft(val)
    return node
  }

  Appendright(val) {
    node := this.root.Appendright(val)
    return node
  }

  ; param: tree's root node
  ; ret:   value list of tree nodes
  ; desc:  root first traverse
  static InOrder(root) {
    static data := IsSet(data) || ''
    if !IsObject(root) {
      return
    } else {
      Tree.InOrder(root.left)
      data .= root.val '`n'
      Tree.InOrder(root.right)
      return data
    }
  }

  ; param: tree's root node
  ; ret:   value list of tree nodes
  ; desc:  level traverse
  static LevelTraverse(root) {
    if root == ''
      return
    q := Queue()
    q.AddVal(root)
    data := ''
    while (!q.IsEmpty()) {
      node := q.poll()
      data .= node.val '`n' 
      if node.left != '' {
        q.AddVal(node.left)
      }
      if node.right != '' {
        q.AddVal(node.right)
      }
    }
    return data
  }

}


if A_LineFile == A_ScriptFullPath {

  dibug := Debug()
  t := Tree('root')

  dibug.Join('--add-sub-node')
  dairy := t.AppendLeft('dairy').AppendLeft('note.txt')
  dairy.AppendRight('note2.txt')
  data := t.Appendright('data').AppendLeft('data.text')
  data.AppendRight('data2').AppendLeft('data2.txt')

  dibug.Join('--traverse-after-add')
  dibug.Join(Tree.InOrder(t.root))
  ; dibug.Join(Tree.LevelTraverse(t.root))
  dibug.Log()
}